package class06;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class Code02_PrintAllSubsquences {
    // 打印字符串的所有子序列
    static List<String> PrintAllSubsquences(String str) {
        List<String> ans = new ArrayList<>();
        String path = "";
        prcess(str.toCharArray(), 0, ans, path);
        return ans;
    }

    /**
     * @param strArr
     * @param index  当前来到i 位置
     * @param ans    i位置后的字符集合
     * @param path：  i 位置前确定的集合
     * @return
     */
    static void prcess(char[] strArr, int index, List<String> ans, String path) {
        // base case
        if (index == strArr.length) {
            ans.add(path);
            return;
        }
        prcess(strArr, index + 1, ans, path);
        prcess(strArr, index + 1, ans, path + strArr[index]);
    }

    // 打印字符串的所有子序列,并且不能重复
    static List<String> PrintAllSubsquencesNo_Repect(String str) {
        Set<String> ans = new HashSet<>();
        String path = "";
        prcess1(str.toCharArray(), 0, ans, path);
        List<String> anslist = new ArrayList<>();
        for (String set : ans) {
            anslist.add(set);
        }
        return anslist;

    }

    static void prcess1(char[] strArr, int index, Set<String> ans, String path) {
        // base case
        if (index == strArr.length) {
            ans.add(path);
            return;
        }
        prcess1(strArr, index + 1, ans, path);
        prcess1(strArr, index + 1, ans, path + strArr[index]);
    }




    public static void main(String[] args) {
        System.out.print(PrintAllSubsquencesNo_Repect("accc")+" ");
        System.out.println();
        System.out.print(PrintAllSubsquences("accc")+" ");
    }
}
